// T是边长类型
template <class T>
struct Dijkstra {
	using i64 = long long;
	using pli = pair<i64, int>;
	const i64 inf = 4e18;

	Dijkstra(int n) : g_(n + 1) {}

	void addEdge(int x, int y, T w = 0) {
		g_[x].emplace_back(y, w);
	}

	vector<i64> work(int s) {
		vector<i64> dis(g_.size(), inf);
		dis[s] = 0;

		priority_queue<pli, vector<pli>, greater<pli>> Q;
		Q.push({0, s});
		while (!Q.empty()) {
			auto [step, vertex] = Q.top();
			Q.pop();
			if (step != dis[vertex]) {
				continue;
			}
			for (auto &[y, w]: g_[vertex]) {
				if (dis[y] > step + w) {
					dis[y] = step + w;
					Q.push({dis[y], y});
				}
			}
		}
		return dis;
	}

	void clearGraph(int n) {
		g_.clear();
		g_.resize(n + 1);
	}
	vector<vector<pair<int, T>>> g_;
};